#include <iostream>
#include <stack>
#include <stdexcept>  // 添加这个头文件以使用runtime_error
using namespace std;

/**
 * 用两个栈实现队列
 * 队列特性：先进先出 (FIFO)
 * 栈特性：后进先出 (LIFO)
 * 
 * 实现思路：
 * 1. 使用两个栈：输入栈(inStack)和输出栈(outStack)
 * 2. 入队操作：直接将元素压入输入栈
 * 3. 出队操作：
 *    - 如果输出栈为空，将输入栈的所有元素弹出并压入输出栈（这样顺序就反转了）
 *    - 然后从输出栈弹出栈顶元素
 */
class StackQueue {
private:
    stack<int> inStack;   // 输入栈，用于入队操作
    stack<int> outStack;  // 输出栈，用于出队操作
    
    /**
     * 将输入栈的所有元素转移到输出栈
     * 这个操作将元素的顺序反转，使得最先进入的元素在输出栈的顶部
     */
    void transfer() {
        // 将输入栈的所有元素依次弹出并压入输出栈
        while (!inStack.empty()) {
            outStack.push(inStack.top());  // 将输入栈栈顶元素压入输出栈
            inStack.pop();                 // 弹出输入栈栈顶元素
        }
    }
    
public:
    StackQueue() {
        cout << "初始化双栈队列" << endl;
    }
    
    /**
     * 入队操作 - 时间复杂度: O(1)
     * 直接将新元素压入输入栈
     */
    void push(int x) {
        cout << "入队元素: " << x << endl;
        inStack.push(x);
    }
    
    /**
     * 出队操作 - 摊还时间复杂度: O(1)
     * 如果输出栈为空，需要先转移元素
     * 然后从输出栈弹出栈顶元素（即队列的队首元素）
     */
    int pop() {
        if (empty()) {
            throw runtime_error("队列为空，无法出队");
        }
        
        // 如果输出栈为空，需要从输入栈转移元素
        if (outStack.empty()) {
            cout << "输出栈为空，开始转移元素..." << endl;
            transfer();
        }
        
        int front = outStack.top();  // 获取队首元素
        outStack.pop();              // 弹出队首元素
        cout << "出队元素: " << front << endl;
        return front;
    }
    
    /**
     * 获取队首元素 - 摊还时间复杂度: O(1)
     */
    int peek() {
        if (empty()) {
            throw runtime_error("队列为空");
        }
        
        // 如果输出栈为空，需要从输入栈转移元素
        if (outStack.empty()) {
            transfer();
        }
        
        return outStack.top();
    }
    
    /**
     * 判断队列是否为空
     */
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
    
    /**
     * 获取队列大小
     */
    int size() {
        return inStack.size() + outStack.size();
    }
    
    /**
     * 打印队列当前状态（用于调试）
     */
    void printStatus() {
        cout << "输入栈大小: " << inStack.size() 
             << ", 输出栈大小: " << outStack.size() 
             << ", 队列是否为空: " << (empty() ? "是" : "否") << endl;
    }
};

/**
 * 测试用两个栈实现的队列
 */
int main() {
    cout << "=== 测试：用两个栈实现队列 ===" << endl;
    StackQueue queue;
    
    // 测试1：基本入队出队操作
    cout << "\n--- 测试1：基本操作 ---" << endl;
    queue.push(1);
    queue.push(2);
    queue.push(3);
    queue.printStatus();
    
    cout << "队首元素: " << queue.peek() << endl;  // 应该输出1
    cout << "出队: " << queue.pop() << endl;       // 应该输出1
    queue.printStatus();
    
    // 测试2：混合操作
    cout << "\n--- 测试2：混合操作 ---" << endl;
    queue.push(4);
    queue.push(5);
    queue.printStatus();
    
    cout << "队首元素: " << queue.peek() << endl;  // 应该输出2
    cout << "出队: " << queue.pop() << endl;       // 应该输出2
    cout << "出队: " << queue.pop() << endl;       // 应该输出3
    queue.printStatus();
    
    // 测试3：连续出队直到空
    cout << "\n--- 测试3：清空队列 ---" << endl;
    while (!queue.empty()) {
        cout << "出队: " << queue.pop() << " ";
    }
    cout << endl;
    queue.printStatus();
    
    // 测试4：重新入队测试
    cout << "\n--- 测试4：重新入队 ---" << endl;
    queue.push(10);
    queue.push(20);
    cout << "队首元素: " << queue.peek() << endl;  // 应该输出10
    cout << "队列大小: " << queue.size() << endl;  // 应该输出2
    
    cout << "\n=== 测试完成 ===" << endl;
    return 0;
}
